LeHavreV1, France, Analysis, bibRecord, 000272

Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue

Identifieur interne : 000272 ( France/Analysis ); précédent : 000271; suivant : 000273

Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue

Auteurs : Zacharie Ales [France] ; Arnaud Knippel [France] ; Alexandre Pauchet [France]

Source :

RBID : Hal:hal-00946469

Descripteurs français

mix :
- Approche polyédrale, partitionnement de graphe.

Abstract

Nous nous intéressons à un problème de K-partitionnement pour des
applications en analyse de dialogues. Les sommets du graphe
correspondent à des motifs qui ont été déterminés lors d'une phase
préalable. Nous cherchons à partitionner ces motifs en K parties tout
en minimisant une fonction linéaire des coûts associés aux arêtes à
l'intérieur des clusters.

Nous nous basons sur une formulation contenant des variables d'arêtes
et de représentants. Ces dernières indiquent pour chaque partie quel
est le sommet de plus petit indice.

Nous montrons que la dimension du polyèdre correspondant dépend du
paramètre K. Dans le cas général où le polyèdre est de dimension
pleine, nous identifions les inégalités de la formulation définissant
des facettes. Nous avons, de plus, étudié trois familles d'inégalités
(les inégalités de 2-partitions, les inégalités "two-chorded cycle"
ainsi que les inégalités d'ensembles dépendants) et identifié les cas
où ces dernières définissent des facettes. Nous montrons, par la
suite, que les inégalités triangulaires qui ne définissent pas des
facettes peuvent être renforcées en y ajoutant une variable de
représentants.

Nous illustrons leur efficacité par des résultats numériques.

Url:

https://hal.archives-ouvertes.fr/hal-00946469

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000775
to stream Hal, to step Curation: 000775
to stream Hal, to step Checkpoint: 000160
to stream Main, to step Merge: 000285
to stream Main, to step Curation: 000284
to stream Main, to step Exploration: 000284
to stream France, to step Extraction: 000272

Links to Exploration step

Hal:hal-00946469

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue</title>
<author><name sortKey="Ales, Zacharie" sort="Ales, Zacharie" uniqKey="Ales Z" first="Zacharie" last="Ales">Zacharie Ales</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName>
<desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
<placeName><settlement type="city">Rouen</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Knippel, Arnaud" sort="Knippel, Arnaud" uniqKey="Knippel A" first="Arnaud" last="Knippel">Arnaud Knippel</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-90" status="VALID"><orgName>Laboratoire de Mathématique de l'INSA de Rouen</orgName>
<orgName type="acronym">LMI</orgName>
<desc><address><addrLine>Normandie Université, INSA de ROUEN, LMI, Av. de l'Université, BP 08, 76801 St Etienne du Rouvray cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://lmi.insa-rouen.fr/</ref>
</desc>
<listRelation><relation active="#struct-358441" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-358441" type="direct"><org type="institution" xml:id="struct-358441" status="INCOMING"><orgName>Institut National des Sciences Appliquées [INSA] - Rouen : EA3226</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Pauchet, Alexandre" sort="Pauchet, Alexandre" uniqKey="Pauchet A" first="Alexandre" last="Pauchet">Alexandre Pauchet</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName>
<desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
<placeName><settlement type="city">Rouen</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00946469</idno>
<idno type="halId">hal-00946469</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00946469</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00946469</idno>
<date when="2014-02-26">2014-02-26</date>
<idno type="wicri:Area/Hal/Corpus">000775</idno>
<idno type="wicri:Area/Hal/Curation">000775</idno>
<idno type="wicri:Area/Hal/Checkpoint">000160</idno>
<idno type="wicri:Area/Main/Merge">000285</idno>
<idno type="wicri:Area/Main/Curation">000284</idno>
<idno type="wicri:Area/Main/Exploration">000284</idno>
<idno type="wicri:Area/France/Extraction">000272</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr">Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue</title>
<author><name sortKey="Ales, Zacharie" sort="Ales, Zacharie" uniqKey="Ales Z" first="Zacharie" last="Ales">Zacharie Ales</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName>
<desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
<placeName><settlement type="city">Rouen</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Knippel, Arnaud" sort="Knippel, Arnaud" uniqKey="Knippel A" first="Arnaud" last="Knippel">Arnaud Knippel</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-90" status="VALID"><orgName>Laboratoire de Mathématique de l'INSA de Rouen</orgName>
<orgName type="acronym">LMI</orgName>
<desc><address><addrLine>Normandie Université, INSA de ROUEN, LMI, Av. de l'Université, BP 08, 76801 St Etienne du Rouvray cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://lmi.insa-rouen.fr/</ref>
</desc>
<listRelation><relation active="#struct-358441" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-358441" type="direct"><org type="institution" xml:id="struct-358441" status="INCOMING"><orgName>Institut National des Sciences Appliquées [INSA] - Rouen : EA3226</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Pauchet, Alexandre" sort="Pauchet, Alexandre" uniqKey="Pauchet A" first="Alexandre" last="Pauchet">Alexandre Pauchet</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName>
<desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
<placeName><settlement type="city">Rouen</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>Approche polyédrale</term>
<term>partitionnement de graphe</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr">Nous nous intéressons à un problème de K-partitionnement pour des
applications en analyse de dialogues. Les sommets du graphe
correspondent à des motifs qui ont été déterminés lors d'une phase
préalable. Nous cherchons à partitionner ces motifs en K parties tout
en minimisant une fonction linéaire des coûts associés aux arêtes à
l'intérieur des clusters.
 Nous nous basons sur une formulation contenant des variables d'arêtes
et de représentants. Ces dernières indiquent pour chaque partie quel
est le sommet de plus petit indice.
 Nous montrons que la dimension du polyèdre correspondant dépend du
paramètre K. Dans le cas général où le polyèdre est de dimension
pleine, nous identifions les inégalités de la formulation définissant
des facettes. Nous avons, de plus, étudié trois familles d'inégalités
(les inégalités de 2-partitions, les inégalités "two-chorded cycle"
ainsi que les inégalités d'ensembles dépendants) et identifié les cas
où ces dernières définissent des facettes. Nous montrons, par la
suite, que les inégalités triangulaires qui ne définissent pas des
facettes peuvent être renforcées en y ajoutant une variable de
représentants.
 Nous illustrons leur efficacité par des résultats numériques.
</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Haute-Normandie</li>
<li>Région Normandie</li>
</region>
<settlement><li>Le Havre</li>
<li>Rouen</li>
</settlement>
<orgName><li>Université de Rouen</li>
<li>Université du Havre</li>
</orgName>
</list>
<tree><country name="France"><region name="Région Normandie"><name sortKey="Ales, Zacharie" sort="Ales, Zacharie" uniqKey="Ales Z" first="Zacharie" last="Ales">Zacharie Ales</name>
</region>
<name sortKey="Knippel, Arnaud" sort="Knippel, Arnaud" uniqKey="Knippel A" first="Arnaud" last="Knippel">Arnaud Knippel</name>
<name sortKey="Pauchet, Alexandre" sort="Pauchet, Alexandre" uniqKey="Pauchet A" first="Alexandre" last="Pauchet">Alexandre Pauchet</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000272 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000272 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/France
   |area=    LeHavreV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-00946469
   |texte=   Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue
}}

This area was generated with Dilib version V0.6.25.
Data generation: Sat Dec 3 14:37:02 2016. Site generation: Tue Mar 5 08:25:07 2024

	Serveur d'exploration sur la visibilité du Havre
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la visibilité du Havre

Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue

Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue

Source :

Descripteurs français

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri